<?php
/**
 * <https://y.st./>
 * Copyright © 2018 Alex Yst <mailto:copyright@y.st>
 * 
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program. If not, see <https://www.gnu.org./licenses/>.
**/

$xhtml = array(
	'<{title}>' => 'Potions?',
	'takedown' => '2017-11-01',
	'<{body}>' => <<<END
<img src="/img/CC_BY-SA_4.0/y.st./weblog/2018/11/30.jpg" alt="Raining on teh bike path" class="framed-centred-image" width="649" height="480"/>
<section id="drudgery">
	<h2>Drudgery</h2>
	<p>
		My discussion post for the day:
	</p>
	<blockquote>
		<p>
			(Last week, someone complained that I cited Wikipedia because it&apos;s &quot;not suitable for academic use&quot;.
			Before you complain this week, take a look at our reading assignment list.
			Part of our reading assignment provided by this university <strong>*is on Wikipedia*</strong>.
			Clearly, this school considers Wikipedia to be a valid place to learn from in an academic setting.
			I&apos;ve had countless courses at this school do the same thing.
			This university accepts information from Wikipedia as valid.)
		</p>
		<h3>Big endian versus little endian</h3>
		<p>
			Big endian keeps the high-order byte at the beginning.
			This is the way we tend to write numbers in our decimal system.
			For example, in the number <code>275</code>, the <code>2</code> is the most-significant digit.
			It has the highest value (being worth <code>200</code>, as opposed to <code>70</code> or <code>5</code> like the other digits), so it goes first.
			International standard dates are like this too.
			YYYY-MM-DD: the year comes first, because it represents the biggest amount of time, then comes the month, and finally the day, as days are smaller than both years and months.
		</p>
		<p>
			Little endian keeps the smallest-order byte at the front.
			It&apos;s somewhat backwards, compared to big endian.
			I have no concrete real-world examples, as we just don&apos;t write our numbers this way outside of computers.
			However, a sort of example would be the date format used in some countries: DD-MM-YYYY.
			The individual three values are each big endian (The year is still <code>2017</code>, not <code>7102</code>), but the order of the values in the trio is little endian, as the least-significant value, the day, comes first while the most-significant value, the year, comes last.
			Little endian has an odd quirk, like the date format in this paragraph.
			The bits in the individual bytes, like the segments in the date, are <strong>*not*</strong> reversed.
		</p>
		<p>
			Speaking of date formats, the date format used commonly in my own country, the United States, is just idiotic.
			Most people here use MM-DD-YYYY.
			There&apos;s no rhyme or reason to the order of the components.
			It&apos;s not big endian, it&apos;s not little endian ... it&apos;s just a mess.
			Medium, then small, then big?
			There&apos;s no justification for that.
			Like the United States&apos; refusal to use the global standard in measurements, the metric system, the United States&apos; use of this date system is both screwy and insane.
			This date format is comparable to if we used <code>653</code> to mean three-hundred sixty-five.
		</p>
		<h3>Advantages and disadvantages of each</h3>
		<p>
			The easiest way to multiply a number by a power of four is to shift the bits to the left (Kjell, n.d.).
			That works when using the big endian format, because all the bits are arranged from greatest to least.
			Likewise, the easiest way to divide by a power of two is to shift all the bits to the right.
			Again, this works with big-endian numbers.
			However, when using the little endian format, bits can&apos;t be shifted that way, as they&apos;re not arranged perfectly according to significance.
			The bytes arranged by significance, and the bits within each byte are arranged by significance, but when the number is taken as a whole, the bits across bytes are in a bizarre order.
			(To be clear, if the bits in the bytes were reversed just like the bytes themselves were reversed, little endian wouldn&apos;t be storing bits in a bizarre order.
			Instead, the bits would be perfectly backwards from big endian, making it simply a matter of which direction you store and read the number.)
		</p>
		<p>
			Honestly, I couldn&apos;t find any advantages to little endian until I specifically performed a Web search for little endian advantages, at which point I found a decent list of the advantages of both.
			I was decently shocked that little endian has advantages, but some of the advantages listed make a lot of sense.
			Personally, I don&apos;t agree with the statement that reading little endian values is easier for people that use right to left languages, which the source gave.
			It certainly would be easier if the bits were ordered from least to most significant, but they&apos;re not.
			Because the bytes are ordered one way and the bits within each byte ordered the opposite way, you&apos;re stuck jumping back and forth while trying to read the number.
			Regardless of what direction you&apos;re used to reading, you&apos;re going to need to read on both directions back and forth to make sense of a little endian value.
		</p>
		<h4>Advantages of big endian values</h4>
		<h5>Easier for humans to read</h5>
		<p>
			My source says it&apos;s only easier for most humans (Phúc, 2018), but let&apos;s be honest: it&apos;s a lot easier to read backwards than it is to read something that&apos;s mixed up in an odd order.
			It&apos;s easier for all <strong>*reasonable*</strong> humans to read big endian.
			If little endian gets fixed to use backwards bits as well as backwards bytes, little endian will be easy to read as well, and will be easier for people that use right-to-left languages.
			In the current state of things though, big endian has little endian beaten in terms of human readability.
		</p>
		<h5>Easier sign checking</h5>
		<p>
			The sign (positive or negative) is stored as the first bit in the most-significant byte, so if the most-significant byte comes first, you can just check the first bit of the number and find the sign (Phúc, 2018).
		</p>
		<h5>Easier inequality testing</h5>
		<p>
			Need to know if a value is greater than or less than another value?
			The most-significant bits are the ones that have the most effect on this.
			The most significant bit that differs between the numbers is the last one you need to check.
			Nothing beyond that needs to be checked.
			So if the bytes are in big-endian order, you can just start fromt he beginning and go down the line until you encounter a difference (Phúc, 2018).
		</p>
		<h5>Network protocols use big endian</h5>
		<p>
			If you&apos;re sending stuff over the network, you&apos;ll probably need to do it in big endian format, regardless of what format your local processor is designed to use (Phúc, 2018).
		</p>
		<h5>Bit shifts</h5>
		<p>
			Like I said above, the sane ordering of big endian makes bit shifts a viable mechanism for performing certain types of maths (Kjell, n.d.).
			This could be fixed in little endian by reversing the bits within each byte, putting little endian bits into a sane order as well.
			In the current little endian standard though, little endian lacks this ability to multiply and divide by powers of two with simple bit shifts.
		</p>
		<h4>Advantages of little endian</h4>
		<h5>Even or odd?</h5>
		<p>
			By checking the last bit of the least-significant byte, you can tell if the number is even or odd.
			In little endian format, this is the first byte, so it&apos;s easier to check (Phúc, 2018).
		</p>
		<h5>Easier to compute</h5>
		<p>
			Typically, you work with the least-significant digits first when doing maths, as the results of the low-order operations can carry over to the high-order operations.
			When using little-endian values, the low-order bytes come first, making this easier (Phúc, 2018).
			However, the lowest-order bit is at the end of the first byte, due to little endian&apos;s bizarre ordering.
			Again, I&apos;d argue that this advantage could be increased by ironing out little endian&apos;s bit order, putting the least-significant bit at the very beginning.
		</p>
		<h5>Truncating</h5>
		<p>
			When a little endian value below the size of the maximum number storable in a smaller size is truncated to that size, it still reads as the same number (Phúc, 2018).
			That is to say, instead of losing your least-significant bits, you lose your most-significant bits, resulting in the same number being stored whenever possible.
			This doesn&apos;t work for larger numbers, but it works for small numbers.
			This results in easier casting from one integer size to another.
			According to my source, it&apos;s basically a no-cost operation.
			This isn&apos;t the case with big-endian numbers.
			In big endian, you have to know how big the value&apos;s storage size is so you can find the end of it and truncate the beginning instead.
		</p>
		<h3>Integer overflow</h3>
		<p>
			Integer overflow is a truncation of the most-significant bits of a number that is too large to fit in the space provided to store an integer.
			Think of a motor vehicle&apos;s odometer.
			It has a set number of digits.
			Integers as represented in a computer have a set number of bits.
			If your odometer has seven digits and it reads <code>9999999</code>, what happens when you go another kilometre (or mile, depending on odometer setup)?
			It reaches <code>10000000</code>, but that&apos;s one too many digits, so the most-significant one, the <code>1</code>,  gets truncated and you&apos;re left with <code>0000000</code>.
			The same thing happens inside a computer.
			When an operation, such as addition or multiplication, results in a number that can&apos;t be represented with the number of bits provided, that number rolls over; it gets truncated.
			For unsigned integers, it&apos;s like performing modulo division on every mathematical result before returning it, where the number you modulo by is the maximum integer size plus one.
			For signed integers, that first bit determines the sign.
			As a result, both overflow and underflow flip the sign, as they change the sign bit.
		</p>
		<p>
			The book tries to make a distinction between signed and unsigned integers, claiming that unsigned integers are simply cyclic, while signed integers have overflow.
			However, this cyclic nature is the very definition of how overflow works; both signed and unsigned integers are cyclic, and for both signed and unsigned integer, this cyclic nature is caused by the presence of overflow (and underflow).
			When you go up above the maximum, you cycle back to the minimum.
			The only difference is that for unsigned integers, the minimum is zero, but for signed integers, the minimum is negative.
			This differentiation is made because the C11 standard claims that unsigned integers can&apos;t overflow (Wikipedia, 2018).
			Instead, they just &quot;saturate&quot;.
			There is no technical difference between saturation and overflow though; saturation <strong>*is*</strong> overflow, just applied to unsigned numbers.
		</p>
		<p>
			The book cautions us about conditionals that rely on values that might have overflowed.
			Additionally, these overflows might not always be our own faults.
			Sometimes, the compiler rearranges our arithmetic in its attempt to optimise, and causes overflow in places the order of operations would normally have prevented it.
			If the conditional is tied to security code, that code might execute the wrong branch (in an <code>if</code>/<code>elseif</code>/<code>else</code> structure or a <code>switch</code> structure) or might not execute at all (especially in the case of loops).
		</p>
		<p>
			Related to overflow, you also have underflow.
			If the number is below the minimum, it rolls around back to the maximum.
		</p>
		<h4>Security</h4>
		<p>
			I honestly couldn&apos;t find any security-specific implications of this.
			Countless potential problems are evident, but nothing related to security was obvious to me.
			Thankfully, other people on the Internet have given great thought to the security implications of overflow.
		</p>
		<p>
			First, we have buffer overflows.
			Integer overflow results in a smaller number than intended, as the intended number is too large to fit into the available space.
			If an integer is used to represent the amount of space that needs to reserved for a value, too small of a space may be reserved (Auger, 2009).
			When the data gets written to the reserved space, it&apos;ll overflow that allotted space and overwrite something else in memory.
			This puts things onto spots on memory where they don&apos;t belong, not to mention that important data might get overwritten.
			An overwrite can happen in a couple ways.
			First, if the next space on disk is already in use, that in-use section can get overwritten.
			Second, the next space on disk <strong>*isn&apos;t*</strong> reserved for the overflowing data.
			That overflowing data can itself be overwritten, either by an update to the value that that memory was already reserved for, or by that section of memory getting reserved for a new piece of data, as that section is seen as unused unless it was reserved for something else before the overflow.
		</p>
		<p>
			Second, we have conditions relating to money.
			Three main scenarios were presented by Auger, but they&apos;re pretty much the same two situations: overflow and underflow.
			If a value is too high and causes overflow in a signed integer, that value can become negative.
			This can reverse the flow of money.
			For example, you could send a negative amount of money to someone else&apos;s account or pay a negative amount for some good or service (Auger, 2009).
			In either case, you&apos;re able to steal money because the bank or credit union thinks you&apos;re <strong>*giving*</strong> money.
			In terms of underflow, an unlikely situation was presented: withdrawing more money than you have.
			In the real world, a bank or credit union would definitely check for this, but if the integer representing your money is unsigned and you have no money, withdrawing money would result in underflow, and your account would now have a lot of money (Auger, 2009).
		</p>
		<h4>My own dealings with overflow</h4>
		<p>
			It&apos;s not exactly related to security, but I&apos;ve been working on a project that has me thinking about the possibility of overflows frequently.
			It&apos;s just a game; nothing of sever importance.
			However, it implements a set of counters for events.
			If these event counters ever overflowed, they&apos;d go negative.
			Think about levelling a character with no level cap, then suddenly your level drops far down into the red.
			It&apos;s not exactly something you want to see happen after putting in a lot of time grinding, right?
			Due to the way the game is programmed (I didn&apos;t write the main game, just some code that adds features), there&apos;s basically three layers of numbers.
			The main layer uses 64-bit doubles.
			In my initial design used a layer on top of that which was provided by the game&apos;s $a[API] that stored values as 32-bit signed integers on disk.
			This automatically implemented overflow.
			I built code around this, which flipped the negative numbers positive again by adding back in 2<sup>32</sup> in cases the number was found negative.
			Still, once you went too high, you&apos;d fall back to zero.
			I considered adding a second counter which would count the number of times you rolled back to zero, which would effectively double the counter size, but never implemented it as I decided it didn&apos;t really fix the fact that there was a limit at which rollover would occur - it only pushed that limit further out in a sort-of-obtuse way.
			And because precision is more important than rollover in this code, I can&apos;t simply cap the code out at negative one (the maximum, after converting back to positive)
		</p>
		<p>
			I eventually replaced the layer that saves values as 32-bit integers with something of my own design that saves the values as strings, and manually implemented overflow myself.
			Because of loss of precision due to this version of Lua having only doubles, and no form of true integers, I still can&apos;t make use of the full 64-bit numeric value.
			However, I get a value range of a little over fifty-five bits, so I don&apos;t realistically fear overflow any more.
			(Due to the point at which integer precision is lost and the way double values are represented, I have access to 55<sup>2</sup>+1 unique values, one value beyond what a fifty-five bit integer can store, and not a clean fifty-five bits.)
			Still, if I ever get reports of resetting back to zero, I&apos;ll need to implement that second counter and assume no one can overflow a <code>18014398509481985</code>-value counter <code>18014398509481985</code> times, resetting <strong>*both*</strong> counters back to zero.
			I don&apos;t anticipate even the first counter overflowing at this point though.
		</p>
		<div class="APA_references">
			<h3>References:</h3>
			<p>
				Auger, R. (2009, December 30). The Web Application Security Consortium / Integer Overflows. Retrieved from <a href="https://projects.webappsec.org/w/page/13246946/Integer%20Overflows"><code>https://projects.webappsec.org/w/page/13246946/Integer%20Overflows</code></a>
			</p>
			<p>
				Kjell, B. (n.d.). Big Endian and Little Endian. Retrieved from <a href="https://chortle.ccsu.edu/AssemblyTutorial/Chapter-15/ass15_3.html"><code>https://chortle.ccsu.edu/AssemblyTutorial/Chapter-15/ass15_3.html</code></a>
			</p>
			<p>
				Phúc, L. V. (2018, March 3). What are the advantages of using Big Endian over Little Endian in a computer architecture? Why do some designers decide to use Big Endian? - Quora. Retrieved from <a href="https://www.quora.com/What-are-the-advantages-of-using-Big-Endian-over-Little-Endian-in-a-computer-architecture-Why-do-some-designers-decide-to-use-Big-Endian"><code>https://www.quora.com/What-are-the-advantages-of-using-Big-Endian-over-Little-Endian-in-a-computer-architecture-Why-do-some-designers-decide-to-use-Big-Endian</code></a>
			</p>
			<p>
				Wikipedia. (2018, September 12). Integer overflow - Wikipedia. Retrieved from <a href="https://en.wikipedia.org/wiki/Integer_overflow"><code>https://en.wikipedia.org/wiki/Integer_overflow</code></a>
			</p>
		</div>
	</blockquote>
</section>
<section id="Minetest">
	<h2>Minetest</h2>
	<p>
		I think I want to revive the alchemy concept I was working on before, but with some changes.
		To start with, no nodes will be added by this mod.
		Everything crafted will be an item with some effect.
		Second, all items crafted will be the <strong>*same*</strong> item, but with a different colour, a different name, and a different effect.
		I think I&apos;ll have the item be potions, and have a witchy, potion-brewing theme.
	</p>
	<p>
		My first issue is figuring out how many items can be brewed together, so I can build the beginning <code>formspec</code> for that page.
		There are twenty-six items.
		There are 16<sup>6</sup> colours.
		Every combination will result in a potion of a different colour.
		For any possible number of items brewed, all possible combinations using that number of items, or any lesser number of items greater than zero, is also allowed.
		The order of the items doesn&apos;t matter, but their count does.
		For example, red mushroom, gold, gold is different from red mushroom, red mushroom, gold, but it&apos;s the same as gold, red mushroom, red mushroom.
		So basically, my task is to mathematically compute what the maximum number of items that can be added to a single potion is.
		Once I&apos;ve found that, I can build the base system, but I won&apos;t actually define all those potions at once!
		I&apos;ll define the twenty-six one-item potions and the three-hundred fifty-one two-item potions.
		I may or may not eve make it to finishing the three-item potions, but I definitely want the <code>formspec</code> and the base system to be ready for the theoretical maximum number of items from the point of initial release.
		Of course, once more elements are added to the game, this maximum will drop, and I will need to update the <code>formspec</code> and base system accordingly, but I want it clear to users that two-item potions were never intended to be the end.
		Once I have my equation, it shouldn&apos;t be hard to update it and figure out when such updates are needed.
	</p>
	<p>
		The other thing I&apos;m doing is drastically simplifying the recipe-unlocking procedure.
		I really like the point-spending mechanic I discussed (and even completely coded) for the unreleased <code>alchemy</code> mod.
		However, it takes up a lot of storage space to keep track of what each player has unlocked.
		Instead, for these potions, a recipe will be unlocked if you&apos;ve mined a number of stacks of each ingredient equal to the number of ingredients in the potion multiplied by the number of times the given ingredient appears.
		For example, in the recipes I mentioned above, these would be considered three-item recipes, despite having two items, because one item appears twice.
		In the recipe with two gold and one mushroom, you&apos;d need to mine three stacks of mushrooms, but three stacks of gold for <strong>*each*</strong> occurrence of gold in the recipe, making a total of six stacks of gold needed.
		Using this mechanic, we can derive whether a given recipe is unlocked from information already stored about the player, instead of storing recipe unlocks separately.
	</p>
	<p>
		<strong>*UPDATE*:</strong> I came up with some better ideas at work.
		First of all, the colour and effect of the potions will be decided by the recipes, so no coming up with 4272047 separate potion effects.
		Each ingredient will have some effect it bestows, and both the number of that item you use as well as your level of proficiency with that item will have an effect on the strength of that particular ability.
		This means you can put multiple effects into one potion, but the more effects you add, the weaker each effect will be.
		Additionally, each ingredient will have a drinking effect and an enchanting effect.
		If you drink the potion, it does one thing, but you can also craft the potions with tools to get some other effect for the tool.
		Only one potion per tool though, making higher-levelled potions valuable, as you can&apos;t simply stack low-level potions to get the same effect.
		The main reason the potions can all be used both ways is that finding a way to dynamically assign one of the two potion types to each potion seems impossibly difficult, so I&apos;ll just do away with separate potion types from the start.
	</p>
	<p>
		I also tried to brute force an answer to the problem I mentioned above, which was to find the maximum number of ingredients that could be used to craft potions with unique colours.
		Before work, I set a script running to try several numbers.
		It didn&apos;t complete before I got home, because it was hopelessly inefficient.
		At work though, I came up with a much more optimised way to get my answer.
		I figured my optimised version would still take a while, but it takes mere seconds to try a number.
		It seems seven ingredients gives me 4272047 potions (the number in the preceding paragraph wasn&apos;t random!), while eight ingredients would give me too many potions, at 18156203 out of 16777216 possible.
	</p>
	<p>
		So yeah, I&apos;ve got to come up with a couple abilities for each ingredient to bestow, one for players and one for tools.
		That&apos;s not a task for tonight though.
		I&apos;ve got about five minutes until midnight at this point.
		I&apos;ve got a couple finer details to work out as well, such as substitute ingredients to use instead of elements I don&apos;t want to use directly (sand, spores, and seeds; I already have substitute ingredients for the saplings, which I don&apos;t want to use directly either).
		I&apos;m also not limiting the potion count any more, and will probably allow nine-ingredient recipes, or maybe ten-ingredient recipes.
	</p>
</section>
END
);
